The present invention relates to a method for generating a subpixel mask for removing an aliasing phenomenon generated when a polygon edge is displayed as a pixel in a computer graphics system, and an apparatus thereof, and more particularly, to a method for generating a subpixel mask for polygon edges directly by an operation without using a look-up table, and an apparatus thereof.
Aliasing is an undesired phenomenon produced in the process of converting various analogical phenomena of nature into discrete values. This applies to a computer graphics system so that polygon edges are displayed so as to have a jagged or staircase appearance, due to the limited number of pixels on the screen of a cathode ray tube. Removing such an aliasing phenomenon is called anti-aliasing, which is implemented by point sampling (or multiple sampling) and area sampling in a computer graphics system. Point sampling is widely used since the hardware implementation thereof is relatively easy. However, when processing polygons which form thin lines or narrowly acute angles, point sampling causes the polygon to appear as a dashed line and entails such problems as a "net effect" phenomenon (see "Computer Graphics: Principle and Practice" by J. Foley and A. van Dam, pp617-623), which occur when the display of a small object moves. On the other hand, a better image quality can be obtained by area sampling in which the contribution of pixels is determined by an exact coverage calculation, but the hardware implementation of such a coverage calculation and the generation of the coverage shape present difficulties.
Meanwhile, an anti-aliasing method using subpixel mask solves the above problems caused by the pointing sampling, by adopting the area concept of area sampling to the conventional point sampling method, which easily achieves the coverage calculation and coverage shape generation. In other words, by displaying the pixel coverage occupied by an arbitrary object within a pixel and displaying the pixel coverage shape as a subpixel mask, since the set mask corresponds to the coverage for the arbitrary object and the coverage shape is stored as a mask, the information for performing the anti-aliasing more efficiently is supplied in case plural objects exist within a pixel.
Typical methods that make use of subpixel mask include an A-buffer algorithm (see "The A-buffer: an Anti-alisased Hidden Surface Method," by Loren Carpenter, Siggraph, 1984, pp103-108). However, according to this method, a subpixel mask (pixel bit mask) is generated in a software process, which entails slow speed. Another method using a subpixel mask is a method using a look-up table (see "A New Simple and Efficient Antialiasing with Subpixel mask," by Andreas Schilling, Siggraph, 1991, pp133-141). In the look-up table method, all possible subpixel mask shapes, which can be generated depending on the slope (de.sub.x) of a triangle's edge and the distance (e) from pixel center to its edge, are prestored in a look-up table. Here, the a subpixel-mask is generated by indexing the look-up table with the above two pieces of information which are calculated when performing a triangle traversal operation, by a method proposed by Juan Pineda (see "A Parallel Algorithm for Polygon Rasterizations," Siggraph, 1988, pp17-20).
FIG. 1 illustrates the traversal of a triangle by the Pineda method. In a triangle formed by three vertices V1, V2 and V3, a pixel moves downward in the Y-axis direction one by one from vertex V2, where scanning is performed left and right, taking the location of the pixel as a base point BP. That is to say, if coordinates (X, Y, Z) of the starting point (vertex V2), RGB color components and the increments of R, G, B and Z values with respect to the X and Y coordinates, are input, the scanning of a pixel moves downward along axis Y by one pixel from the top vertex V2. Here, the data value of each advancing pixel is calculated to perform a leftward scanning with respect to base point BP. Then, when scanning reaches the edge, the scanning of pixels returns to base point BP and then a similar scanning to the right is performed. When scanning reaches the triangle's other edge, the scanning returns to the base point again to then be incremented by one pixel along the Y axis, whereupon left and right scanning is repeated and moves downward along the Y axis. In the Pineda method, by calculating the distance from pixel center C to the edge, it is determined whether the edge is reached. That is to say, if the calculated value is positive, it is determined that the scanned pixel lies inside the triangle, and if negative, it is determined that the pixel is beyond the edge and scanning returns to the base point BP.
FIG. 2 is a diagram showing a pixel divided into 4.times.4 subpixels, that is, sixteen subpixels (from 0 to 15). Here, each pixel is switched on or off depending on the pixel coverage, which thereby generates a set of subpixel mask.
FIGS. 3A, 3B and 3C illustrate the concept of the conventional subpixel mask generator using the look-up table as proposed by Schilling, by adopting the method of FIG. 1. Here, FIG. 3A shows the slope de.sub.x of an edge as it moves across a pixel having a center C, wherein the edge is at a distance e from the pixel's center. Then, in FIG. 3B, the information of FIG. 3A is input to a look-up table and 16-bit data is output for generating a subpixel mask, which results in FIG. 3C showing one 4.times.4 subpixel mask corresponding to the edge position of FIG. 3A.
According to the conventional method for generating a subpixel mask using the look-up table, 4.times.4 subpixel mask generation requires total eleven bits for expressing parameters, with five bits for the polygon edge parameter e which is the distance from the pixel center to the polygon edge, four bits assigned for the parameter de.sub.x (the e variation with respect to .DELTA.X) and two sign bits: one de.sub.x sign bit and one bit for the sign of de.sub.y (the e variation with respect to .DELTA.Y). Therefore, a 2.sup.11 .times.16-bit memory is necessary for constituting the polygon edge by a look-up table, and the look-up table for generating an 8.times.8 subpixel mask requires fifteen bits to express the necessary parameters, which means that the memory capacity must be 2.sup.15 .times.64 bits. Furthermore, in practice, as three edges form a basic triangular polygon, 2.sup.11 .times.16.times.3-bit memories are necessary for implementing by the look-up table method. Hence, with such large memories being necessary, the fabrication of application-specific intergrated circuit (ASIC) for the hardware implementation of a graphics algorithm is quite cumbersome.